#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-
'''
Copyright (C) 2010 Anderson Tiago, Caio Almeida, Efraim Machado, dcc.ufba.br

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

MATA65 - Computer Graphics 
Universidade Federal da Bahia - 2010.1
Weiler-Atherton Clipping Algorithm
'''
import math, inkex, simplestyle
from simplepath import *

class weilerAtherton(inkex.Effect):
  
  # Just gets parameters
  def __init__(self):
    inkex.Effect.__init__(self)
    self.OptionParser.add_option("-o", "--operation",
      action="store", type="string",
      dest="operation", default="union",
      help="Operação a ser realizada entre os polígonos")
  
  def effect(self):
    svg = self.document.getElementsByTagName('svg')[0]
    
    # Only do something if there are elements selected in Inkscape
    if self.selected:
      polygons, n = [{ "id" : None, "v" : [], "e" : [], "node" : None }, { "id" : None, "v" : [], "e" : [], "node" : None }], 0
      
      # Only two polygons by turn, the others are ignored
      for id, node in self.selected.iteritems():
        polygons[n]["id"] = id
        polygons[n]["node"] = node
        n += 1
        if n == 2:
          break
      
      ops = {
          'A-B' : 'difference',
          'B-A' : 'difference2',
          'União' : 'union',
          'Interseção' : 'intersection'
      }
      self.options.operation = ops[self.options.operation]

      # Store the vertex set as a list, assuming that all commands are lineto
      for p in polygons:
        
        # Now the attribute v stores the list of coordinates pairs of the polygon
        # [ [x1,y1], [x2,y2], ... ]
        p["v"] = []
        for edge in parsePath(p["node"].getAttribute('d')):
          command, coordinates = edge
          if len(coordinates) > 0:
            p["v"].append(coordinates)
        
        # Now the attribute e stores the list of edges of the polygon
        # [ [ [x1,y1], [x2,y2] ], [ [x2,y2], [x3,y3] ], ... ]
        p["e"] = []
        previous = p["v"][0]
        for vertex in p["v"][1:]:
          p["e"].append([previous, vertex])
          previous = vertex
      
      # Plot our result polygon(s)
      if self.options.operation == 'intersection':
        for inter in self.operations(polygons[0]["e"], polygons[1]["e"], self.options.operation):
          self.drawResult(inter)
      else:
        self.drawResult(self.operations(polygons[0]["e"], polygons[1]["e"], self.options.operation))

  def drawResult(self, polygon):
    pol_style = {
      'fill' : 'gray'
    }
    svg = self.document.getElementsByTagName('svg')[0]
    resultpol = self.document.createElement('path')
    points = []
    for pair in polygon:
      points.append(",".join([str(pair[0]),str(pair[1])]))
    d = 'M ' + ' L '.join(points) + ' z'
    resultpol.setAttribute('d', d)
    resultpol.setAttribute('id', 'clip')
    resultpol.setAttribute('style',simplestyle.formatStyle(pol_style))
    svg.appendChild(resultpol)
  
  def operations(self, polygon1, polygon2, operation):
    poligono1 = []
    pol1      = []
    poligono2 = []
    pol2      = []
    inter     = []

    debug = False

    for p in polygon1:
      poligono1.append(p[0])
    
    for p in polygon2:
      poligono2.append(p[0])
  
    if operation == 'difference2':
      poligono1, poligono2 = poligono2, poligono1
    
    pol1 = poligono1[:]
    pol2 = poligono2[:]

    #print poligono1,"\n", poligono2
    
    for p2 in poligono2:
      indice2 = poligono2.index(p2)
      if indice2+1 >= len(poligono2):
        indice2 = -1
      p2_prox = poligono2[indice2+1]
      #print p, " ", p_prox  
      if p2[0] == p2_prox[0]:
        semCoef2 = True
      else:
        semCoef2 = False
        coefReta2 = float(p2_prox[1] - p2[1])/float(p2_prox[0] - p2[0])
        bReta2 = coefReta2*(-p2[0]) + p2[1]
      
      for p1 in poligono1:
        indice1 = poligono1.index(p1)
        if indice1+1 >= len(poligono1):
          indice1 = -1
        p1_prox = poligono1[indice1+1]
        #print p1, " ", p1_prox, " indice ", indice1+1
        if p1[0] == p1_prox[0]:
          semCoef1 = True
        else:
          semCoef1 = False
          coefReta1 = float(p1_prox[1] - p1[1])/float(p1_prox[0] - p1[0])
          bReta1 = coefReta1*(-p1[0]) + p1[1]
        
        if (p1 == p2) and (p1_prox == p2_prox):
          #print p1, " ", p2, " pertencem a intersecao"
          if (p1) not in inter:  
            inter.append(p1)
          if (p1_prox) not in inter:  
            inter.append(p1_prox)
        else:
          if (semCoef2 == True) and (semCoef1 == True):
            if (debug == True):        
              print "retas paralelas...."
          else:
            if semCoef1 == True and semCoef2 == False:
              xInter = p1[0]
              coef = coefReta2
              b    = bReta2
    
            elif semCoef2 == True and semCoef1 == False:
              xInter = p2[0]
              coef = coefReta1
              b    = bReta1
    
            elif coefReta1 == coefReta2:
              if debug == True:  
                print "Retas paralelas nao se interseptam"
              continue
            else:    
              xInter = float(bReta2 - bReta1)/float(coefReta1 - coefReta2)
              coef = coefReta1
              b = bReta1

            yInter = coef*xInter + b
            #print "[", xInter, ",", yInter, "] eh um possivel ponto do poligono"
            if yInter >= min(p1[1], p1_prox[1]) and yInter <= max(p1[1], p1_prox[1]) and yInter >= min(p2[1], p2_prox[1]) and yInter <= max(p2[1], p2_prox[1]) and xInter >= min(p1[0], p1_prox[0]) and xInter <= max(p1[0], p1_prox[0]) and xInter >= min(p2[0], p2_prox[0]) and xInter <= max(p2[0], p2_prox[0]):
              #print "[", xInter, ",", yInter, "] eh ponto do poligono de intersecao" 
    
              #crio lista com todos os pontos de interseção (fora de ordem)
              if ([xInter,yInter]) not in inter:  
                inter.append([xInter,yInter])
    
              if ([xInter,yInter]) not in pol1:
                for pAux in pol1:
                  i = pol1.index(pAux)
                  if i+1 >= len(pol1):
                    i = -1
                  pAuxProx = pol1[i+1]
                  #print "testando [", xInter, ",",yInter,"] contra ", pAux, " ", pAuxProx
                  if pAux[0] == pAuxProx[0]:
                    if xInter == pAux[0]:
                      if yInter >= min(pAux[1], pAuxProx[1]) and yInter <= max(pAux[1], pAuxProx[1]) and xInter >= min(pAux[0], pAuxProx[0]) and xInter <= max(pAux[0], pAuxProx[0]):
                        pol1.insert(i+1, [xInter, yInter])
                        break
                  else:
                    coefR = float(pAuxProx[1] - pAux[1])/float(pAuxProx[0]-pAux[0])
                    bR = coefR*(-pAux[0]) + pAux[1]
                    #print yInter, " == ", (coefR*xInter+bR)
                    if round(yInter, 2) == round((coefR*xInter+bR), 2):
                        if yInter >= min(pAux[1], pAuxProx[1]) and yInter <= max(pAux[1], pAuxProx[1]) and xInter >= min(pAux[0], pAuxProx[0]) and xInter <= max(pAux[0], pAuxProx[0]):
                          pol1.insert(i+1, [xInter, yInter])
                          break
              if ([xInter,yInter]) not in pol2:
                for pAux in pol2:
                  i = pol2.index(pAux)
                  if i+1 >= len(pol2):
                    i = -1
                  pAuxProx = pol2[i+1]
                  if pAux[0] == pAuxProx[0]:
                    if xInter == pAux[0]:
                      if yInter >= min(pAux[1], pAuxProx[1]) and yInter <= max(pAux[1], pAuxProx[1]) and xInter >= min(pAux[0], pAuxProx[0]) and xInter <= max(pAux[0], pAuxProx[0]):
                        pol2.insert(i+1, [xInter, yInter])
                        break
                  else:
                    coefR = float(pAuxProx[1] - pAux[1])/float(pAuxProx[0]-pAux[0])
                    bR = coefR*(-pAux[0]) + pAux[1]
                    #print yInter, " == ", (coefR*xInter+bR)
                    if round(yInter,2) == round((coefR*xInter+bR),2):
                        if yInter >= min(pAux[1], pAuxProx[1]) and yInter <= max(pAux[1], pAuxProx[1]) and xInter >= min(pAux[0], pAuxProx[0]) and xInter <= max(pAux[0], pAuxProx[0]):
                          pol2.insert(i+1, [xInter, yInter])
    
                          break
    #print "pontos do poligono interseção", inter          
    #print "pol1 ", pol1        
    #print "pol2 ", pol2          
    #corrigindo listas, caso necessário
    while pol1[0] != poligono1[0]:
      x = pol1[0]
      pol1=pol1[1:]
      pol1.append(x)
    while pol2[0] != poligono2[0]:
      x = pol2[0]
      pol2=pol2[1:]
      pol2.append(x)
    
    #print "pol1 ", pol1        
    #print "pol2 ", pol2
    
    indice = 0
    lista = pol2
    numIntersecao = 0
    polIntersecao = [[]]
    entrada = []
    saida = []
    a = False
    
    for p in pol2:
      if p in inter:
        if not a:
          
          entrada.append(p)
          a = True
        else:
          saida.append(p)    
          a = not a
          
    
    #print "lista dos pontos de entrada", entrada
    #print "lista dos pontos de saida", saida
    
    resultado = []
    poligonoAtual = []
    
    while (entrada):  
    
      visitante = lista[indice]
    
      if visitante not in entrada:
        indice = indice + 1
        if indice >= len(lista):
          indice = 0
      else:
        poligonoAtual.append(visitante)
        entrada.remove(visitante)
        
        indice = indice + 1
        if indice >= len(lista):
          indice = 0
        visitante = lista[indice]      
        
        while visitante not in saida:
          poligonoAtual.append(visitante)
          indice = indice + 1
          if indice >= len(lista):
            indice = 0
          visitante = lista[indice]
    
        poligonoAtual.append(visitante)
    
        if lista == pol1:
          lista = pol2
        else:
          lista = pol1
    
        indice = lista.index(visitante)+1
    
        if indice >= len(lista):
          indice = 0
    
        visitante = lista[indice]
    
        while visitante not in inter:
          poligonoAtual.append(visitante)
          indice = indice + 1
          if indice >= len(lista):
            indice = 0
          visitante = lista[indice]
        
        #poligonoAtual.append(visitante)
    
        if visitante in poligonoAtual:
          resultado.append(poligonoAtual)
          poligonoAtual = []
          if not entrada:
            if (debug == True):
              print "FIM DAS INTERSECOES"
        if lista == pol1:
          lista = pol2
        else:
          lista = pol1
    
    #print "intersecoes ", resultado
    
    #diferenca
    indice = 0
    diferenca = []
    lista = pol2
    incremento = 1
    visitante = lista[0]
    
    while visitante not in diferenca:
      diferenca.append(visitante)
      if visitante in inter:
        if lista == pol2:
          lista = pol1
          incremento = -1
        else:
          lista = pol2
          incremento = 1
        indice = lista.index(visitante)
      if indice+incremento < 0:
        indice = len(lista) -1
      elif indice+incremento >= len(lista):
        indice = 0
      else:   
        indice = indice + incremento
      visitante = lista[indice]
    
    #print "diferenca ", diferenca
    
    #uniao
    indice = 0
    lista = pol2
    visitante = lista[0]
    uniao = []
    
    while visitante not in uniao:
      uniao.append(visitante)
      if visitante in inter:
        if lista == pol2:
          lista = pol1
        else:
          lista = pol2
        indice = lista.index(visitante)
      if indice + 1 >= len(lista):
        indice = 0
      else:   
        indice = indice + 1
      visitante = lista[indice]
    
    if operation == 'union':
      return uniao
    elif operation == 'intersection':
      return resultado
    else:
      return diferenca
    
  # Just for debugging
  def debug(self, something = "DEBUG"):
    svg = self.document.getElementsByTagName('svg')[0]
    label = self.document.createElement('text')
    text = self.document.createTextNode(repr(something))
    label.appendChild(text)
    svg.appendChild(label)

# Applies the effect
e = weilerAtherton()
e.affect()
